SYSREGS = ['RS', 'RC0']
SYM_ARITH = {'PLUS': '+', 'MINUS': '-', 'MUL': '*', 'DIV': '/', 'MOD': '%'}
SYM_COND = {'EQ': '=', 'NE': '><', 'GT': '>', 'GE': '>=', 'LT': '<', 'LE': '<='}
INV_ARITH = {'PLUS': 'MINUS', 'MINUS': 'PLUS'}
INV_COND = {'EQ': 'NE', 'NE': 'EQ', 'GT': 'LE', 'GE': 'LT', 'LT': 'GE', 'LE': 'GT',
             'ET': 'OU', 'OU': 'ET', 'VRAI': 'FAUX', 'FAUX': 'VRAI'}
TOKEN_COND_ATO = {'EQ', 'NE', 'GT', 'GE', 'LT', 'LE'}
TOKEN_COND = TOKEN_COND_ATO | {'ET', 'OU', 'NON', 'FAUX', 'VRAI'}
ARR_ERR_CODE = -1

class CompileError(Exception):
  pass

class ParseError(CompileError):
  pass

def compile(tok, achk, usetape):
  env=Env(tok, achk, usetape)
  env.parse()
#  env.print_ptree() # debug
  env.optimize()
#  env.print_ptree() # debug
  env.compile()
  return env.code, env.macros

def macro_gvar(id):
  return 'G'+id

def macro_lvar(fid, vid):
  return 'VL!{0}@{1}'.format(fid, vid)

def macro_a(id):
  return 'A'+id

def macro_as(id):
  return 'AS'+id

def label_fid(id):
  return 'L!'+id

def label_lab(fid, lid):
  return '{0}@{1}'.format(label_fid(fid), lid)

class label_next:
  def __init__(self):
    self.n=0
  def __call__(self, n=None):
    if n is None:
      ret='L'+str(self.n)
      self.n+=1
      return ret
    else:
      assert n>0
      ret=tuple(['L'+str(self.n+i) for i in range(n)])
      self.n+=n
      return ret

class Tokens:
  def __init__(self, tok):
    self.tok=tok
  def __len__(self):
    return len(self.tok)
  def ttype(self, n=0):
    if n<len(self.tok):
      return self.tok[n][0]
  def shiftok(self):
    self.tok=self.tok[1:]
  def chktok(self, type):
    t=self.ttype()
    if t!=type:
      self.perror()
    if t:
      ret=self.tok[0][1]
      self.shiftok()
      return ret
  def sep(self):
    t=self.ttype()
    if t=='NL':
      self.shiftok()
    elif t=='SEMI':
      self.shiftok()
      self.ttype()=='NL' and self.shiftok()
    else:
      self.perror()
  def perror(self):
    t=self.ttype()
    if t:
      raise ParseError('parse error at {0} (line {1})'.format(t, self.tok[0][2]))
    else:
      raise ParseError('cannot get next token')

class Env:
  def __init__(self, tok, achk=True, usetape=False):
    self.tok, self.achk, self.usetape = Tokens(tok), achk, usetape
    self.gvars=set()
    self.macros={v: i for i, v in enumerate(SYSREGS)}
    self.arrs={}
    self.lenv={}
    self.funcs={}
    self.main=None
    self.label_next=label_next()
    self.code=None
  class LEnv:
    pass
  def lenv_init_set(self, fid):
    self.lenv_init(fid)
    self.lenv_set(fid)
  def lenv_init(self, fid):
    self.lenv[fid]=Env.LEnv()
    self.lenv[fid].lvars=set()
    self.lenv[fid].labs={}
  def lenv_set(self, fid):
    self.fid=fid
    self.lvars=self.lenv[fid].lvars
    self.labs=self.lenv[fid].labs
  def gvar_add(self, id):
    self.gvars.add(id)
  def lvar_add(self, id):
    self.lvars.add(id)
  def arr_decl(self, id, a):
    assert len(a)>0
    if self.arrs.get(id):
      raise CompileError("array {0} is already declared".format(id))
    self.arrs[id]=a
  def arr_add(self, id):
    self.arrs.setdefault(id)
  def label_decl(self, id):
    if self.labs.get(id):
      raise CompileError('label {0} is already appeared in {1}'.format(id, self.fid))
    self.labs[id]=True
  def label_add(self, id):
    self.labs.setdefault(id, False)
  def func_decl(self, fd):
    if fd.id in self.funcs:
      f=self.funcs[fd.id]
      if not isinstance(f, fdecl_dummy):
        raise CompileError('function {0} is already defined'.format(fd.id))
      elif fd.pnum!=f.pnum:
        raise CompileError("argument number error ({0})".format(fd.id))
    self.funcs[fd.id]=fd
  def func_add(self, id, pnum):
    if id not in self.funcs:
      self.funcs[id]=fdecl_dummy(id, pnum)
    elif pnum!=self.funcs[id].pnum:
      raise CompileError('argument number error ({0})'.format(id))
  def macro_add(self, key, val):
    assert key not in self.macros
    self.macros[key]=val
  def parse(self):
    tok=self.tok
    while True:
      t=tok.ttype()
      if t=='ARRAY':
        parse_adecl(self)
      elif t=='FUNCTION':
        parse_fdecl(self)
      else:
        break
    parse_main(self)
    if tok.ttype() is not None:
      tok.perror()
  def optimize(self):
    assert self.main
    self.main=self.main.optimize()
    for k, v in self.funcs.items():
      self.funcs[k]=v.optimize()
  def compile(self):
    assert self.main
    for i, id in enumerate(self.gvars):
      self.macro_add(macro_gvar(id), len(SYSREGS)+i)
    acode=[]
    for k, v in self.arrs.items():
      if v is None:
        raise CompileError("array {0} is not declared".format(k))
      self.macro_add(macro_a(k), len(SYSREGS)+len(self.gvars)+len(acode)-1)
      self.macro_add(macro_as(k), len(v))
      acode.extend(v)
    fcode=[]
    for k, v in self.funcs.items():
      if isinstance(v, fdecl_dummy):
        raise CompileError('function {0} is not defined'.format(v.id))
      fcode.extend(v.compile(self, 0))
    l=self.label_next()
    code = [0]*(len(SYSREGS)+len(self.gvars))
    code.extend(acode)
    code[SYSREGS.index('RS')] = len(code)
    code.append(('jmp', l))
    code.extend(fcode)
    code.append(('lab', l))
    code.extend(self.main.compile(self, 0))
    code.append(('hal', 0))
    self.code=code
  def print_ptree(self):
    for k, v in self.arrs.items():
      print('ARRAY {0} {1}'.format(k, v))
    for v in self.funcs.values():
      print(v)
    print(self.main)

class node:
  def optimize(self):
    return self

class fdecl_dummy(node):
  def __init__(self, id, pnum):
    self.id, self.pnum=id, pnum
  def __str__(self):
    return 'FUNCTION_DUMMY {0}({1})'.format(self.id, self.pnum)

class fdecl(node):
  def __init__(self, id, args, body):
    self.id=id
    self.args, self.pnum = args, len(args)
    self.body=body
  def __str__(self):
    return 'FUNCTION {0}({1}) {2}'.format(self.id, ', '.join(self.args), self.body)
  def compile(self, env, depth):
    fid=self.id
    env.lenv_set(fid)
    for k, v in env.labs.items():
      if not v:
        raise CompileError('label {0} is not defined in {1}'.format(k, fid))
    env.macro_add(macro_lvar(fid, fid), -(3+len(SYSREGS)+self.pnum))
    for i, v in enumerate(self.args):
      env.macro_add(macro_lvar(fid, v), i-len(self.args))
    rlvars=env.lvars.difference([fid]+self.args)
    assert 1+self.pnum+len(rlvars)==len(env.lvars)
    for i, v in enumerate(rlvars):
      env.macro_add(macro_lvar(fid, v), i)
    ret=[('lab', label_fid(fid))]
    ret.append(('sal', len(rlvars)))
    ret.extend(self.body.compile(env, depth+len(rlvars)))
    ret.append(('pop', len(rlvars)+self.pnum))
    ret.extend(('gto', i) for i in reversed(SYSREGS))
    ret.append('jpo')
    return ret
  def optimize(self):
    return fdecl(self.id, self.args, self.body.optimize())

class main(node):
  def __init__(self, body):
    self.body=body
    self.id='MAIN'
  def __str__(self):
    return '{0} {1}'.format(self.id, self.body)
  def compile(self, env, depth):
    fid=self.id
    env.lenv_set(fid)
    for k, v in env.labs.items():
      if not v:
        raise CompileError('label {0} is not defined in {1}'.format(k, fid))
    for i, vid in enumerate(env.lvars):
      env.macro_add(macro_lvar(fid, vid), i)
    ret=[('sal', len(env.lvars))]
    ret.extend(self.body.compile(env, depth+len(env.lvars)))
    return ret
  def optimize(self):
    return main(self.body.optimize())

class body(node):
  def __init__(self, children=[]):
    self.children=children
  def __str__(self):
    return ' '.join([str(a) for a in self.children])
  def compile(self, env, depth):
    ret=[]
    for a in self.children:
      ret.extend(a.compile(env, depth))
    return ret
  def optimize(self):
    return body([n.optimize() for n in self.children])

class writes(node):
  def __init__(self, exp):
    self.exp=exp
  def __str__(self):
    return '{{ WRITE {0} }}'.format(self.exp)
  def compile(self, env, depth):
    ret=self.exp.compile(env, depth)
    ret.append('pri')
    return ret
  def optimize(self):
    return writes(self.exp.optimize())

class exits(node):
  def __init__(self, exp):
    self.exp=exp
  def __str__(self):
    return '{{ EXIT {0} }}'.format(self.exp)
  def compile(self, env, depth):
    ret=self.exp.compile(env, depth)
    ret.append('hal')
    return ret
  def optimize(self):
    return exits(self.exp.optimize())

class adain(node):
  def __init__(self, id, ind, exp):
    self.id, self.ind, self.exp = id, ind, exp
  def __str__(self):
    return '{{ {0}[{1}] := {2} }}'.format(self.id, self.ind, self.exp)
  def compile(self, env, depth):
    ret=self.exp.compile(env, depth)
    ret.extend(self.ind.compile(env, depth+1))
    ret.extend(chkaind(env, self.id))
    ret.append(macro_a(self.id))
    ret.append('add')
    ret.append('gto')
    return ret
  def optimize(self):
    return adain(self.id, self.ind.optimize(), self.exp.optimize())

class gdain(node):
  def __init__(self, id, exp):
    self.id, self.exp = id, exp
  def __str__(self):
    return '{{ ${0} := {1} }}'.format(self.id, self.exp)
  def compile(self, env, depth):
    ret=self.exp.compile(env, depth)
    ret.append(('gto', macro_gvar(self.id)))
    return ret
  def optimize(self):
    return gdain(self.id, self.exp.optimize())

class ldain(node):
  def __init__(self, id, exp):
    self.id, self.exp = id, exp
  def __str__(self):
    return '{{ {0} := {1} }}'.format(self.id, self.exp)
  def compile(self, env, depth):
    ret=self.exp.compile(env, depth)
    ret.extend([('god', 'RS'), macro_lvar(env.fid, self.id), 'add', 'gto'])
    return ret
  def optimize(self):
    return ldain(self.id, self.exp.optimize())

class tdain(node):
  def __init__(self, ind, exp):
    self.ind, self.exp = ind, exp
  def __str__(self):
    return '{{ TAPE[{0}] := {1} }}'.format(self.ind, self.exp)
  def compile(self, env, depth):
    ret=self.exp.compile(env, depth)
    ret.extend(self.ind.compile(env, depth+1))
    ret.append('tto')
    return ret
  def optimize(self):
    return tdain(self.ind.optimize(), self.exp.optimize())

class gread(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return '{{ READ ${0} }}'.format(self.id)
  def compile(self, env, depth):
    return ['red', ('gto', macro_gvar(self.id))]

class lread(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return '{{ READ {0} }}'.format(self.id)
  def compile(self, env, depth):
    return ['red', ('god', 'RS'), macro_lvar(env.fid, self.id), 'add', 'gto']

class aread(node):
  def __init__(self, id, ind):
    self.id, self.ind = id, ind
  def __str__(self):
    return '{{ READ {0}[{1}] }}'.format(self.id, self.ind)
  def compile(self, env, depth):
    id, ind = self.id, self.ind
    ret=['red']
    ret.extend(ind.compile(env, depth+1))
    ret.extend(chkaind(env, id))
    ret.append(macro_a(id))
    ret.append('add')
    ret.append('gto')
    return ret
  def optimize(self):
    return aread(self.id, self.ind.optimize())

class tread(node):
  def __init__(self, ind):
    self.ind = ind
  def __str__(self):
    return '{{ READ TAPE[{0}] }}'.format(self.ind)
  def compile(self, env, depth):
    ret=['red']
    ret.extend(self.ind.compile(env, depth+1))
    ret.append('tto')
    return ret
  def optimize(self):
    return tread(self.ind.optimize())

class whiles(node):
  def __init__(self, con, body):
    self.con, self.body = con, body
  def __str__(self):
    return '{{ WHILE {0} : {1} }}'.format(self.con, self.body)
  def compile(self, env, depth):
    l0, l1 = env.label_next(2)
    ret=[('lab', l0)]
    ret.extend(self.con.compile(env, depth))
    ret.append(('jpo', l1))
    ret.extend(self.body.compile(env, depth))
    ret.append(('jmp', l0))
    ret.append(('lab', l1))
    return ret
  def optimize(self):
    return whiles(self.con.optimize(), self.body.optimize())

class ifs(node):
  def __init__(self, elf, els):
    self.elf, self.els = elf, els
  def __str__(self):
    s=['IF {0[0]} : {0[1]}'.format(self.elf[0])]
    s.extend('ELF {0[0]} : {0[1]}'.format(a) for a in self.elf[1:])
    self.els and s.append('ELSE : {0}'.format(self.els))
    return '{{ {0} }}'.format(' '.join(s))
  def compile(self, env, depth):
    lend=env.label_next()
    ret=[]
    for c, b in self.elf:
      l=env.label_next()
      ret.extend(c.compile(env, depth))
      ret.append(('jpo', l))
      ret.extend(b.compile(env, depth))
      ret.append(('jmp', lend))
      ret.append(('lab', l))
    if self.els:
      ret.extend(self.els.compile(env, depth))
    ret.append(('lab', lend))
    return ret
  def optimize(self):
    elf_new = [(b[0].optimize(), b[1].optimize()) for b in self.elf]
    else_new = self.els.optimize() if self.els else None
    return ifs(elf_new, else_new)

class proc(node):
  def __init__(self, func):
    self.func=func
  def __str__(self):
    return '{{ {0} }}'.format(self.func)
  def compile(self, env, depth):
    ret=self.func.compile(env, depth)
    ret.append('pop')
    return ret
  def optimize(self):
    return proc(self.func.optimize())

class gotos(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return '{{ GOTO {0} }}'.format(self.id)
  def compile(self, env, depth):
    return [('jmp', label_lab(env.fid, self.id))]

class labels(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return '{{ LABEL {0} }}'.format(self.id)
  def compile(self, env, depth):
    return [('lab', label_lab(env.fid, self.id))]

class cond_b:
  def __init__(self, conds, op):
    assert len(conds)>=2
    self.conds, self.op = conds, op
  def __str__(self):
    return '{{ {0} }}'.format((' '+self.op+' ').join([str(t) for t in self.conds]))

class cond_ou(node, cond_b):
  def __init__(self, conds):
    cond_b.__init__(self, conds, 'OU')
  def compile(self, env, depth):
    ret=self.conds[0].compile(env, depth)
    for c in self.conds[1:]:
      l1, l2 = env.label_next(2)
      ret.append(('jpo', l1))
      ret.append(0)
      ret.append(('jmp', l2))
      ret.append(('lab', l1))
      ret.extend(c.compile(env, depth))
      ret.append(('lab', l2))
    return ret
  def optimize(self):
    return cond_ou([a.optimize() for a in self.conds])
  def non(self):
    return cond_et([cond_non(a) for a in self.conds])

class cond_et(node, cond_b):
  def __init__(self, conds):
    cond_b.__init__(self, conds, 'ET')
  def compile(self, env, depth):
    ret=self.conds[0].compile(env, depth)
    for c in self.conds[1:]:
      l1, l2 = env.label_next(2)
      ret.append(('jpo', l1))
      ret.extend(c.compile(env, depth))
      ret.append(('jmp', l2))
      ret.append(('lab', l1))
      ret.append(1)
      ret.append(('lab', l2))
    return ret
  def optimize(self):
    return cond_et([a.optimize() for a in self.conds])
  def non(self):
    return cond_ou([cond_non(a) for a in self.conds])

class cond_non(node):
  def __init__(self, c):
    self.c=c
  def __str__(self):
    return '{{ NON {0} }}'.format(self.c)
  def compile(self, env, depth):
    ret=self.c.compile(env, depth+1)
    ret.insert(0, 1)
    ret.append('sub')
    return ret
  def optimize(self):
    return self.c.non().optimize()
  def non(self):
    return self.c

class cond_ato(node):
  def __init__(self, e1, op, e2):
    self.e1, self.op, self.e2 = e1, op, e2
  def __str__(self):
    return '{{ {0} {1} {2} }}'.format(self.e1, SYM_COND[self.op], self.e2)
  def compile(self, env, depth):
    if self.op=='EQ':
      l1, l2 = env.label_next(2)
      ret=self.e1.compile(env, depth)
      ret.extend(self.e2.compile(env, depth+1))
      ret.append('sub')
      ret.append(('gto', 'RC0'))
      ret.append(('god', 'RC0'))
      ret.append(('jpo', l1))
      ret.append(0)
      ret.append(('god', 'RC0'))
      ret.append('sub')
      ret.append(('jmp', l2))
      ret.append(('lab', l1))
      ret.append(1)
      ret.append(('lab', l2))
    elif self.op=='NE':
      l1, l2 = env.label_next(2)
      ret=self.e1.compile(env, depth)
      ret.extend(self.e2.compile(env, depth+1))
      ret.append('sub')
      ret.append(('gto', 'RC0'))
      ret.append(('god', 'RC0'))
      ret.append(('jpo', l1))
      ret.append(('god', 'RC0'))
      ret.append(1)
      ret.append('add')
      ret.append(('jmp', l2))
      ret.append(('lab', l1))
      ret.append(0)
      ret.append(('lab', l2))
    elif self.op=='GT':
      ret=self.e2.compile(env, depth)
      ret.extend(self.e1.compile(env, depth+1))
      ret.append('sub')
      ret.append(1)
      ret.append('add')
    elif self.op=='GE':
      ret=self.e2.compile(env, depth)
      ret.extend(self.e1.compile(env, depth+1))
      ret.append('sub')
    elif self.op=='LT':
      ret=self.e1.compile(env, depth)
      ret.extend(self.e2.compile(env, depth+1))
      ret.append('sub')
      ret.append(1)
      ret.append('add')
    else:
      assert self.op=='LE'
      ret=self.e1.compile(env, depth)
      ret.extend(self.e2.compile(env, depth+1))
      ret.append('sub')
    return ret
  def optimize(self):
    return cond_ato(self.e1.optimize(), self.op, self.e2.optimize())
  def non(self):
    return cond_ato(self.e1, INV_COND[self.op], self.e2)

class vrai(node):
  def __str__(self):
    return 'VRAI'
  def compile(self, env, depth):
    return [0]
  def non(self):
    return faux()

class faux(node):
  def __str__(self):
    return 'FAUX'
  def compile(self, env, depth):
    return [1]
  def non(self):
    return vrai()

class exp_b:
  def __init__(self, exps, ops):
    assert len(ops)>0 and len(exps)==len(ops)+1
    self.exps, self.ops = exps, ops
  def __str__(self):
    a=['{0} {1}'.format(e, SYM_ARITH[o]) for e, o in zip(self.exps, self.ops)]
    a.append(str(self.exps[-1]))
    return '{{ {0} }}'.format(' '.join(a))

class exp_e(node, exp_b):
  def compile(self, env, depth):
    ret=self.exps[0].compile(env, depth)
    for op, exp in zip(self.ops, self.exps[1:]):
      ret.extend(exp.compile(env, depth+1))
      if op=='PLUS':
        ret.append('add')
      else:
        assert op=='MINUS'
        ret.append('sub')
    return ret
  def optimize(self):
    exps_new=[a.optimize() for a in self.exps]
    ops_new=self.ops[:]
    if isinstance(exps_new[0], exp_u):
      assert exps_new[0].op=='MINUS'
      exps_new[0]=exps_new[0].exp
      for i in range(len(ops_new)):
        if isinstance(exps_new[i+1], exp_u):
          assert exps_new[i+1].op=='MINUS'
          exps_new[i+1]=exps_new[i+1].exp
        else:
          ops_new[i]=INV_ARITH[ops_new[i]]
      return exp_u('MINUS', exp_e(exps_new, ops_new))
    else:
      for i in range(len(ops_new)):
        if isinstance(exps_new[i+1], exp_u):
          assert exps_new[i+1].op=='MINUS'
          exps_new[i+1]=exps_new[i+1].exp
          ops_new[i]=INV_ARITH[ops_new[i]]
      return exp_e(exps_new, ops_new)

class exp_f(node, exp_b):
  def compile(self, env, depth):
    ret=self.exps[0].compile(env, depth)
    for op, exp in zip(self.ops, self.exps[1:]):
      if op=='MUL':
        ret.extend(exp.compile(env, depth+1))
        ret.append('mul')
      elif op=='DIV':
        ret.extend(exp.compile(env, depth+1))
        ret.append('div')
      else:
        assert op=='MOD'
        ret.extend([('gto', 'RC0'), ('god', 'RC0'), ('god', 'RC0')])
        ret.extend(exp.compile(env, depth+2))
        ret.extend([('gto', 'RC0'), ('god', 'RC0'),
                    'div', ('god', 'RC0'),
                    'mul', 'sub'])
    return ret
  def optimize(self):
    exps_new=[a.optimize() for a in self.exps]
    m=isinstance(exps_new[0], exp_u)
    if m:
      assert exps_new[0].op=='MINUS'
      exps_new[0]=exps_new[0].exp
    for i in range(len(self.ops)):
      if isinstance(exps_new[i+1], exp_u):
        assert exps_new[i+1].op=='MINUS'
        exps_new[i+1]=exps_new[i+1].exp
        if self.ops[i]=='MUL' or self.ops[i]=='DIV':
          m=not m
        else:
          assert self.ops[i]=='MOD'
    return exp_u('MINUS', exp_f(exps_new, self.ops)) if m else exp_f(exps_new, self.ops)

class exp_u(node):
  def __init__(self, op, exp):
    self.op, self.exp = op, exp
  def __str__(self):
    return '{{ {0} {1} }}'.format(SYM_ARITH[self.op], self.exp)
  def compile(self, env, depth):
    if self.op=='PLUS':
      ret=self.exp.compile(env, depth)
    else:
      assert self.op=='MINUS'
      ret=self.exp.compile(env, depth+1)
      ret.insert(0, 0)
      ret.append('sub')
    return ret
  def optimize(self):
    exp=self.exp.optimize()
    if self.op=='PLUS':
      return exp
    assert self.op=='MINUS'
    if isinstance(exp, num):
      return num(-exp.val)
    elif isinstance(exp, exp_u):
      assert exp.op=='MINUS'
      return exp.exp
    else:
      return exp_u('MINUS', exp)

class lvar(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return self.id
  def compile(self, env, depth):
    return [('god', 'RS'), macro_lvar(env.fid, self.id), 'add', 'god']

class gvar(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return '$'+self.id
  def compile(self, env, depth):
    return [('god', macro_gvar(self.id))]

class tvar(node):
  def __init__(self, ind):
    self.ind = ind
  def __str__(self):
    return 'TAPE[{0}]'.format(self.ind)
  def compile(self, env, depth):
    ret=self.ind.compile(env, depth)
    ret.append('tod')
    return ret
  def optimize(self):
    return tvar(self.ind.optimize())

class avar(node):
  def __init__(self, id, ind):
    self.id, self.ind = id, ind
  def __str__(self):
    return '{0}[{1}]'.format(self.id, self.ind)
  def compile(self, env, depth):
    ret=self.ind.compile(env, depth)
    ret.extend(chkaind(env, self.id))
    ret.append(macro_a(self.id))
    ret.append('add')
    ret.append('god')
    return ret
  def optimize(self):
    return avar(self.id, self.ind.optimize())

class asize(node):
  def __init__(self, id):
    self.id=id
  def __str__(self):
    return '|{0}|'.format(self.id)
  def compile(self, env, depth):
    return [macro_as(self.id)]

class num(node):
  def __init__(self, val):
    self.val=val
  def __str__(self):
    return str(self.val)
  def compile(self, env, depth):
    return [self.val]

class func(node):
  def __init__(self, id, params):
    self.id, self.params, self.pnum = id, params, len(params)
  def __str__(self):
    s=', '.join([str(a) for a in self.params])
    return '{0}({1})'.format(self.id, s)
  def compile(self, env, depth):
    l=env.label_next()
    ret=[0, 1, l]
    ret.extend(('god', j) for j in SYSREGS)
    for i, a in enumerate(self.params):
      ret.extend(a.compile(env, depth+3+len(SYSREGS)+i))
    ret.append(('god', 'RS'))
    ret.append(depth+3+len(SYSREGS)+self.pnum)
    ret.append('add')
    ret.append(('gto', 'RS'))
    ret.append(('jmp', label_fid(self.id)))
    ret.append(('lab', l))
    return ret
  def optimize(self):
    return func(self.id, [a.optimize() for a in self.params])

def parse_fdecl(env):
  tok=env.tok
  tok.chktok('FUNCTION')
  fid=tok.chktok('ID')
  env.lenv_init_set(fid)
  env.lvar_add(fid)
  tok.chktok('LPAR')
  args=[]
  if tok.ttype()!='RPAR':
    while True:
      id=tok.chktok('ID')
      if id==fid or id in args:
        raise CompileError("argument {0} already exists".format(id))
      args.append(id)
      if tok.ttype()=='COMMA':
        tok.shiftok()
        continue
      break
  for a in args:
    env.lvar_add(a)
  tok.chktok('RPAR')
  tok.sep()
  bo=get_body(env)
  tok.chktok('END')
  tok.sep()
  env.func_decl(fdecl(fid, args, bo))

def parse_adecl(env):
  tok=env.tok
  tok.chktok('ARRAY')
  id=tok.chktok('ID')
  t=tok.ttype()
  if t=='LBRA':
    tok.shiftok()
    k=getanum(env)
    if k<=0:
      raise CompileError('{0}: array size must be positive'.format(id))
    a=[0]*k
    tok.chktok('RBRA')
    tok.sep()
  elif t=='DEF':
    tok.shiftok()
    tok.chktok('LBRA')
    a=[getanum(env)]
    while tok.ttype()=='COMMA':
      tok.shiftok()
      a.append(getanum(env))
    tok.chktok('RBRA')
    tok.sep()
  else:
    tok.perror()
  env.arr_decl(id, a)

def getanum(env):
  tok=env.tok
  t=tok.ttype()
  if t=='PLUS':
    tok.shiftok()
    return tok.chktok('NUM')
  elif t=='MINUS':
    tok.shiftok()
    return -tok.chktok('NUM')
  else:
    return tok.chktok('NUM')

def parse_main(env):
  env.lenv_init_set('MAIN')
  env.main=main(get_body(env))

def get_body(env):
  tok=env.tok
  a=[]
  while True:
    t, t1 = tok.ttype(), tok.ttype(1)
    if t=='WRITE':
      a.append(get_writes(env))
    elif t=='DOLLAR':
      a.append(get_gdain(env))
    elif t=='ID' and t1=='DEF':
      a.append(get_ldain(env))
    elif t=='ID' and t1=='LBRA':
      a.append(get_adain(env))
    elif t=='ID' and t1=='LPAR':
      a.append(get_proc(env))
    elif t=='IF':
      a.append(get_ifs(env))
    elif t=='WHILE':
      a.append(get_whiles(env))
    elif t=='READ':
      a.append(get_reads(env))
    elif t=='GOTO':
      a.append(get_gotos(env))
    elif t=='LABEL':
      a.append(get_labels(env))
    elif env.usetape and t=='LBLO':
      a.append(get_tdain(env))
    elif t=='EXIT':
      a.append(get_exits(env))
    else:
      break
  return body(a)

def get_writes(env):
  tok=env.tok
  tok.chktok('WRITE')
  exp=get_e(env)
  tok.sep()
  return writes(exp)

def get_exits(env):
  tok=env.tok
  tok.chktok('EXIT')
  exp=get_e(env)
  tok.sep()
  return exits(exp)

def get_gdain(env):
  tok=env.tok
  tok.chktok('DOLLAR')
  id=tok.chktok('ID')
  tok.chktok('DEF')
  exp=get_e(env)
  tok.sep()
  env.gvar_add(id)
  return gdain(id, exp)

def get_ldain(env):
  tok=env.tok
  id=tok.chktok('ID')
  tok.chktok('DEF')
  exp=get_e(env)
  tok.sep()
  env.lvar_add(id)
  return ldain(id, exp)

def get_adain(env):
  tok=env.tok
  id=tok.chktok('ID')
  tok.chktok('LBRA')
  ind=get_e(env)
  tok.chktok('RBRA')
  tok.chktok('DEF')
  exp=get_e(env)
  tok.sep()
  env.arr_add(id)
  return adain(id, ind, exp)

def get_tdain(env):
  tok=env.tok
  tok.chktok('LBLO')
  ind=get_e(env)
  tok.chktok('RBLO')
  tok.chktok('DEF')
  exp=get_e(env)
  tok.sep()
  return tdain(ind, exp)

def get_reads(env):
  tok=env.tok
  tok.chktok('READ')
  if tok.ttype()=='DOLLAR':
    tok.shiftok()
    id=tok.chktok('ID')
    tok.sep()
    env.gvar_add(id)
    return gread(id)
  if env.usetape and tok.ttype()=='LBLO':
    tok.shiftok()
    ind=get_e(env)
    tok.chktok('RBLO')
    tok.sep()
    return tread(ind)
  id=tok.chktok('ID')
  if tok.ttype()=='LBRA':
    tok.shiftok()
    ind=get_e(env)
    tok.chktok('RBRA')
    tok.sep()
    env.arr_add(id)
    return aread(id, ind)
  else:
    tok.sep()
    env.lvar_add(id)
    return lread(id)

def get_whiles(env):
  tok=env.tok
  tok.chktok('WHILE')
  co=get_conds(env)
  tok.sep()
  bo=get_body(env)
  tok.chktok('END')
  tok.sep()
  return whiles(co, bo)

def get_ifs(env):
  tok=env.tok
  tok.chktok('IF')
  con=get_conds(env)
  tok.sep()
  body=get_body(env)
  elf=[(con, body)]
  while tok.ttype()=='ELSIF':
    tok.shiftok()
    con=get_conds(env)
    tok.sep()
    body=get_body(env)
    elf.append((con, body))
  t=tok.ttype()
  if t=='ELSE':
    tok.shiftok()
    tok.sep()
    body=get_body(env)
    tok.chktok('END')
    tok.sep()
    els=body
  elif t=='END':
    tok.shiftok()
    tok.sep()
    els=None
  else:
    tok.perror()
  return ifs(elf, els)

def get_proc(env):
  tok=env.tok
  f=get_func(env)
  tok.sep()
  return proc(f)

def get_gotos(env):
  tok=env.tok
  tok.chktok('GOTO')
  id=tok.chktok('ID')
  tok.sep()
  env.label_add(id)
  return gotos(id)

def get_labels(env):
  tok=env.tok
  tok.chktok('LABEL')
  id=tok.chktok('ID')
  tok.sep()
  env.label_decl(id)
  return labels(id)

def get_conds(env):
  tok=env.tok
  conds=[get_et(env)]
  while tok.ttype()=='OU':
    tok.shiftok()
    conds.append(get_et(env))
  return cond_ou(conds) if len(conds)>=2 else conds[0]

def get_et(env):
  tok=env.tok
  conds=[get_cond(env)]
  while tok.ttype()=='ET':
    tok.shiftok()
    conds.append(get_cond(env))
  return cond_et(conds) if len(conds)>=2 else conds[0]

def get_cond(env):
  tok=env.tok
  t=tok.ttype()
  if t=='VRAI':
    tok.shiftok()
    return vrai()
  elif t=='FAUX':
    tok.shiftok()
    return faux()
  elif t=='NON':
    tok.shiftok()
    return cond_non(get_cond(env))
  elif t=='LPAR':
    p=1
    for q in range(1, len(tok)):
      t0=tok.ttype(q)
      if t0 in TOKEN_COND:
        tok.shiftok()
        ret=get_conds(env)
        tok.chktok('RPAR')
        return ret
      elif t0=='LPAR':
        p+=1
      elif t0=='RPAR':
        p-=1
        if p==0:
          break
    else:
      tok.perror()
  e1=get_e(env)
  op=tok.ttype()
  if op not in TOKEN_COND_ATO:
    tok.perror()
  tok.shiftok()
  e2=get_e(env)
  return cond_ato(e1, op, e2)

def get_e(env):
  tok=env.tok
  exps=[get_f(env)]
  ops=[]
  while True:
    t=tok.ttype()
    if t=='PLUS' or t=='MINUS':
      tok.shiftok()
      exps.append(get_f(env))
      ops.append(t)
    else:
      break
  return exp_e(exps, ops) if len(ops)>0 else exps[0]

def get_f(env):
  tok=env.tok
  exps=[get_g(env)]
  ops=[]
  while True:
    t=tok.ttype()
    if t=='MUL' or t=='DIV' or t=='MOD':
      tok.shiftok()
      exps.append(get_g(env))
      ops.append(t)
    else:
      break
  return exp_f(exps, ops) if len(ops)>0 else exps[0]

def get_g(env):
  tok=env.tok
  t=tok.ttype()
  if t=='NUM':
    ret=num(tok.chktok('NUM'))
  elif t=='PLUS' or t=='MINUS':
    tok.shiftok()
    ret=exp_u(t, get_g(env))
  elif t=='LPAR':
    tok.shiftok()
    ret=get_e(env)
    tok.chktok('RPAR')
  elif t=='DOLLAR':
    tok.shiftok()
    id=tok.chktok('ID')
    env.gvar_add(id)
    ret=gvar(id)
  elif t=='ID':
    t1=tok.ttype(1)
    if t1=='LBRA':
      id=tok.chktok('ID')
      tok.shiftok()
      ind=get_e(env)
      tok.chktok('RBRA')
      env.arr_add(id)
      ret=avar(id, ind)
    elif t1=='LPAR':
      ret=get_func(env)
    else:
      id=tok.chktok('ID')
      env.lvar_add(id)
      ret=lvar(id)
  elif t=='PIPE':
    tok.shiftok()
    id=tok.chktok('ID')
    tok.chktok('PIPE')
    env.arr_add(id)
    ret=asize(id)
  elif env.usetape and t=='LBLO':
    tok.shiftok()
    ind=get_e(env)
    tok.chktok('RBLO')
    ret=tvar(ind)
  else:
    tok.perror()
  return ret

def get_func(env):
  tok=env.tok
  id=tok.chktok('ID')
  tok.chktok('LPAR')
  params=[]
  if tok.ttype()!='RPAR':
    params.append(get_e(env))
    while tok.ttype()=='COMMA':
      tok.shiftok()
      params.append(get_e(env))
  tok.chktok('RPAR')
  env.func_add(id, len(params))
  return func(id, params)

def chkaind(env, id):
  if not env.achk:
    return []
  l0, l1 = env.label_next(2)
  return [('gto', 'RC0'),
          ('god', 'RC0'), ('jpo', l1),
          ('lab', l0), ('hal', ARR_ERR_CODE),
          ('lab', l1), ('god', 'RC0'), macro_as(id), 'sub', ('jpo', l0),
          ('god', 'RC0')]
